BZOJ 1106 立方体大作战tet

Description

一个叫做立方体大作战的游戏风靡整个Byteotia。这个游戏的规则是相当复杂的,所以我们只介绍他的简单规则:给定玩家一个有2n个元素的栈,元素一个叠一个地放置。这些元素拥有n个不同的编号,每个编号正好有两个元素。玩家每次可以交换两个相邻的元素。如果在交换之后,两个相邻的元素编号相同,则将他们都从栈中移除,所有在他们上面的元素都会掉落下来并且可以导致连锁反应。玩家的目标是用最少的步数将方块全部消除。

Input

一个叫做立方体大作战的游戏风靡整个Byteotia。这个游戏的规则是相当复杂的,所以我们只介绍他的简单规则:给定玩家一个有2n个元素的栈,元素一个叠一个地放置。这些元素拥有n个不同的编号,每个编号正好有两个元素。玩家每次可以交换两个相邻的元素。如果在交换之后,两个相邻的元素编号相同,则将他们都从栈中移除,所有在他们上面的元素都会掉落下来并且可以导致连锁反应。玩家的目标是用最少的步数将方块全部消除。

Output

输出文件第一行包含一个数m,表示最少的步数。

Sample Input

样例输入1
5
5
2
3
1
4
1
4
3
5
2
样例输入2
3
1
2
3
1
2
3

Sample Output

样例输出1
2
样例输出2
3

Hint


Solution

发现如果不是数据结构题用到的数据结构基本上和题目都已经没有什么卵关系了QAQ
把相同的元素在一维平面上连起来
发现合法的解是这些线段没有交
考虑一对元素之间的点全都把线段连出去了
那么显然这些元素不经过一次交换一定不能消掉这一对
一共交换中间的元素个数次,也是与这个线段相交的线段个数个
然后考虑一个大的区间,内部有一些线段,用上面方法解决掉,那么变成一个可以用上面方法解决的区间
最后结论就是直接求线段交点个数Orz
//为什么有些人瞎基本猜就猜得对QAQ

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>

#define maxn 100000+5
#define set(a,b) memset(a,(b),sizeof(a))

using namespace std;

typedef long long ll;

int bit[maxn];
int a[maxn],first[maxn],second[maxn];
int n,ans;

void add(int x,int w)
{

for(int i=x;i<=2*n;i+=i&-i)
bit[i]+=w;
}

int sum(int x)
{

int res=0;
for(int i=x;i>0;i-=i&-i)
res+=bit[i];
return res;
}

int main()
{

#ifndef ONLINE_JUDGE
freopen("1106.in","r",stdin);
freopen("1106.out","w",stdout);
#endif
scanf("%d",&n);
for(int i=1;i<=2*n;i++){
scanf("%d",&a[i]);
if( !first[a[i]] ) first[a[i]]=i;
else second[a[i]]=i;
}
for(int i=1;i<=2*n;i++)
if( i==first[a[i]] ){
ans+=sum(second[a[i]])-sum(first[a[i]]);
add(first[a[i]],-1),add(second[a[i]],1);
}
printf("%d",ans);
return 0;
}